package com.leetcode.August;


/**
 * @Description: 31. 下一个排列
 * @Author: Mr.Fxy
 * 从后向前找到第一个不满足降序排列的元素 nums[i]。
 * 找到 nums[i] 后面比它大的最小元素 nums[j]。
 * 交换这两个元素 nums[i] 和 nums[j]。
 * 将 nums[i+1:] 部分反转，使得这部分成为升序排列。
 * @CreateTime: 2024-08-10 08:34
 */
public class LC31下一个排列 {
    public void nextPermutation(int[] nums) {
        int i=nums.length-2;
        while (i>=0&&nums[i]>=nums[i+1]){
            i--;
        }
        if(i>0){
            int j=nums.length-1;
            while (j>=0 && nums[j]<=nums[i]){
                j--;
            }
            swap(nums,i,j);
        }
        reverse(nums, i + 1, nums.length - 1);
    }
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    private static void reverse(int[] nums, int start, int end) {
        while (start < end){
            swap(nums, start,end);
            start++;
            end--;
        }
    }
}
